#pragma once
#include <vector>
#include <queue>
#include <iostream>
#include <limits>
#include "ErrorCodeDefine.h"

struct Tree
{
	int LeftSon, RightSon,  Size, Value, Key, cnt;
	Tree(int _Value) : Value(_Value), Key(std::rand()), cnt(0), Size(0), LeftSon(0), RightSon(0) {}
};
class TreapTree
{
public:
	int CurrentSize;              //树当前大小
	TreapTree() :CurrentSize(0), Root(0){}
    ECOperateResult Insert(int Value);   //函数对外接口
	ECOperateResult Delete(int Value);  //函数对外接口
	int FindRank(int Value);  //函数对外接口
	int FindValue(int Rank);  //函数对外接口
	int FindSuccessor(int Node);   //函数对外接口
	int FindPredecessor(int Node);  //函数对外接口
protected:
	int Size;                           //树的最大容量                  
	int Root;                            //树根编号
	std::vector<Tree> TreeItem;                  //树的容器
	ECOperateResult LeftRotate(int& Node);        //左旋
	ECOperateResult RightRotate(int& Node);       //右旋
	ECOperateResult UpdateSize(int& Node);        //更新节点
	ECOperateResult Insert(int Value, int& Root);   //传入需要插入的节点权重与根节点
	ECOperateResult Delete(int Value, int& Root);  //传入需要删除的节点与根节点
	int FindRank(int Value, int Root);  //传入节点的权重，返回节点的排名
	int FindValue(int Rank, int Root);  //传入查询节点的排名，返回该节点的权重
	int CreatNewNode(int Value);        //传入一个权重，创建一个新节点，返回节点编号
	int FindSuccessor(int Node, int Root);   //传入一个节点的权重与根节点，返回比这个节点大的最小的数
	int FindPredecessor(int Node, int Root);  //传入一个节点的权重与根节点，返回比这个节点小的最大的数
};

